package tree;

import java.util.*;

/**
 * @author liuchaoqun
 * @date 2022/7/18
 * @Description 中序遍历
 */
public class MidList {

    public static void main(String[] args) {
        // 构建一个二叉树 根左右
        TreeNode root = new TreeNode();
        root.val = 1;
        root.right = new TreeNode();
        root.right.val = 2;
        root.right.left = new TreeNode(3);
        root.right.right = new TreeNode(4);

        System.out.println("中序遍历");
        preOrder(root);
        System.out.println();
        System.out.print("递归层高:");System.out.println(height(root));
        System.out.print("广度优先用队列BFS层高:");System.out.println(BFS(root));
        System.out.print("深度优先使用栈栈求层高:");System.out.println(DFS(root));


    }

    private static Integer DFS(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> level = new Stack<>();
        stack.push(root);
        level.push(1);
        Integer max = 0;
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            Integer temp = level.pop();
            max = Math.max(max, temp);
            if (pop.right != null) {
                stack.push(pop.right);
                level.push(temp + 1);
            }
            if (pop.left != null) {
                stack.push(pop.left);
                level.push(temp + 1);
            }
        }
        return max;
    }

    public static Integer BFS(TreeNode treeNode) {
        Deque<TreeNode> queue = new LinkedList<>();
        queue.push(treeNode);
        Integer count = 0;
        while (!queue.isEmpty()) {
            Integer size = queue.size();
            while (size-- > 0) {
                TreeNode pop = queue.pop();
                if (pop.left != null) {
                    queue.push(pop.left);
                }
                if (pop.right != null) {
                    queue.push(pop.right);

                }
            }
            count++;
        }
        return count;
    }

    public static Integer height(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }
        return Math.max(height(treeNode.left), height(treeNode.right)) + 1;
    }
    public static void preOrder(TreeNode node) {
        if (node == null) {
            return;
        } else {
            System.out.print(node.val);
            preOrder(node.left);
            preOrder(node.right);

        }
    }

}
